Forma normale congiuntiva

Questa pagina sull'argomento matematica sembra trattare argomenti unificabili alla pagina Forma canonica (algebra di Boole).

---

Puoi contribuire unendo i contenuti in una pagina unica. Commenta la procedura di unione usando questa pagina di discussione. Segui i suggerimenti del progetto di riferimento.

Questa voce o sezione sull'argomento logica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Questa voce sull'argomento logica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

Nella logica booleana, una formula è in forma normale congiuntiva o congiunta (FNC), indicata anche come CNF (acronimo di Conjunctive Normal Form) se è una congiunzione di clausole, dove le clausole sono una disgiunzione di letterali. Una formula in CNF ha quindi la seguente struttura:

${\displaystyle \bigwedge _{i=1}^{n}\left(\bigvee _{k=1}^{m(i)}L_{i,k}\right)}$

${\displaystyle n}$ : Numero di clausole.

${\displaystyle m(i)}$ : Numero di letterali della clausola i-esima.

${\displaystyle L_{i,k}}$ : È il k-esimo letterale della i-esima clausola. Un letterale può essere una variabile booleana (cioè che può valere solo 0 o 1, vero o falso) o la negazione di una variabile.

Una funzione booleana è una funzione che ha in ingresso diversi valori booleani (cioè vero/falso oppure 1/0) e come risultato ha un valore booleano. Per ogni funzione booleana, esiste una formula in forma normale congiuntiva che produce come risultato gli stessi valori.